#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode() {
	dest = -1;
	link = NULL;
}

EdgeNode::EdgeNode(int Dest, EdgeNode* Link) {
	dest = Dest;
	link = Link;
}

EdgeNode::~EdgeNode() {
	dest = -1;
	if (link) {
		delete link; link = NULL;
	}
}

int EdgeNode::getDest() {
	return dest;
}

EdgeNode* EdgeNode::getNext() {
	return link;
}

void EdgeNode::setDest(int Dest) {
	dest = Dest;
}

void EdgeNode::setNext(EdgeNode* Link) {
	link = Link;
}

VertexNode::VertexNode() {
	data = '\0';
	firstEdge = NULL;
}

VertexNode::VertexNode(char Data, EdgeNode* FirstEdge) {
	data = Data;
	firstEdge = FirstEdge;
}

VertexNode::~VertexNode() {
	data = '\0';
	if (firstEdge) {
		delete firstEdge; firstEdge = NULL;
	}
}

char VertexNode::getData() {
	return data;
}

EdgeNode* VertexNode::getFirstEdge() {
	return firstEdge;
}

void VertexNode::setData(char data) {
	this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge) {
	firstEdge->setNext(this->firstEdge);
	this->firstEdge = firstEdge;
}

MyGraph::MyGraph() {
	nodeNum = 0; edgeNum = 0;
	VexList = NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList) {
	this->nodeNum = nodeNum; this->edgeNum = edgeNum;
	VexList = new VertexNode[nodeNum];
	for (int i = 0; i < nodeNum; i++)
	{
		VexList[i].setData(nodeList[i]);
	}
	for (int i = 0; i < edgeNum; i++)
	{
		EdgeNode* newNode = new EdgeNode(edgeEndList[i], NULL);
		VexList[edgeStartList[i]].setFirstEdge(newNode);
		newNode = new EdgeNode(edgeStartList[i], NULL);
		VexList[edgeEndList[i]].setFirstEdge(newNode);
	}
}

MyGraph::~MyGraph() {
	nodeNum = 0; edgeNum = 0;
	if (VexList) {
		delete[]VexList; VexList = NULL;
	}
}

int MyGraph::getNodeNum() {
	return nodeNum;
}

int MyGraph::getEdgeNum() {
	return edgeNum;
}

string MyGraph::printGraph() {
	string str;
	for (int i = 0; i < nodeNum; i++)
	{
		str.push_back(VexList[i].getData());
		str += ": ";
		EdgeNode* cur = VexList[i].getFirstEdge();
		while (cur) {
			str.push_back(VexList[cur->getDest()].getData());
			str.push_back(' ');
			cur = cur->getNext();
		}
        str.pop_back();
		if (i != nodeNum - 1)
			str.push_back('\n');
	}
	return str;
}

int MyGraph::getFirstNeighbor(int v, int* visited) {
	if (VexList[v].getFirstEdge())
		return VexList[v].getFirstEdge()->getDest();
	else return -1;
}

int MyGraph::getNextNeighbor(int v, int w, int* visited) {
	EdgeNode* cur = VexList[v].getFirstEdge();
	while (cur->getDest() != w)
	{
		cur = cur->getNext();
	}
	if (!cur->getNext())
		return -1;
	cur = cur->getNext();
	return cur->getDest();
}

void MyGraph::DFS(int v, int* visited, string& result) {
	result.push_back(VexList[v].getData());
	result.push_back(' ');
	visited[v] = 1;
	int w = getFirstNeighbor(v, visited);
	while (w != -1)
	{
		if (!visited[w])DFS(w, visited, result);
		w = getNextNeighbor(v, w, visited);
	}
}

string MyGraph::graph_DFS_Traverse() {
	string result;
	int* visited = new int[nodeNum];
	for (int i = 0; i < nodeNum; i++)visited[i] = 0;
	for (int i = 0; i < nodeNum; i++)
	{
		if (!visited[i])DFS(i, visited, result);
	}
	delete[]visited;
	return result;
}

void MyGraph::BFS(int v, int* visited, string& result) {
	result.push_back(VexList[v].getData());
	result.push_back(' ');
	visited[v] = 1;
	queue<int>q;
	q.push(v);
	while (!q.empty())
	{
		v = q.front();
		q.pop();
		int w = getFirstNeighbor(v, visited);
		while (w != -1)
		{
			if (!visited[w]) {
				result.push_back(VexList[w].getData());
				result.push_back(' ');
				visited[w] = 1;
				q.push(w);
			}
			w = getNextNeighbor(v, w, visited);
		}
	}

}

string MyGraph::graph_BFS_Traverse() {
	string result;
	int* visited = new int[nodeNum];
	for (int i = 0; i < nodeNum; i++)visited[i] = 0;
	for (int i = 0; i < nodeNum; i++)
	{
		if (!visited[i])BFS(i, visited, result);
	}
	delete[]visited;
	return result;
}
